# 单词搜索： https://leetcode-cn.com/problems/word-search/

# 我自己的写法， 使用 nonlocal
class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        """ 以每一个 字符串首字母开头的字符， 在二维矩阵中进行深度优先搜索，查找是否有合适的 """

        flag = False
        def isExist(board, x, y, idx):
            """
                x, y 表示当前坐标
                idx 表示当前 找到字符串的 哪个字符的下标
            """
            nonlocal flag
            # 1. 当前满足这样，都直接结束
            if board[x][y] != word[idx] or board[x][y] == '':
                return 
            
            tempC = board[x][y]
            # 标记以使用过，不能重复使用
            board[x][y] = ''

            # 2. 如果等于 idx 结束
            if idx == len(word) - 1:
                flag = True
                return 

            # 3. 继续寻找下一个 idx
            # 向上
            if x - 1 >= 0:
                isExist(board, x - 1, y, idx + 1)
            # 向右
            if y + 1 < len(board[0]):
                isExist(board, x, y + 1, idx + 1)
            # 向左
            if y - 1 >= 0:
                isExist(board, x, y - 1, idx + 1)        
            # 向下
            if x + 1 < len(board):
                isExist(board, x + 1, y, idx + 1)

            # 4. 回溯，解除当前位置的修改    
            board[x][y] = tempC

        for i in range(len(board)):
            for j in range(len(board[0])):
                if board[i][j] == word[0]:
                    isExist(board, i, j, 0)
                if flag:
                    return flag

        return flag


# 不用 nonlocal 的写法
class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        """ 以每一个 字符串首字母开头的字符， 在二维矩阵中进行深度优先搜索，查找是否有合适的 """

        flag = False
        def isExist(board, x, y, idx):
            """
                x, y 表示当前坐标
                idx 表示当前 找到字符串的 哪个字符的下标
            """
            # 1. 当前满足这样，都直接结束
            if board[x][y] != word[idx] or board[x][y] == '':
                return False
            
            tempC = board[x][y]
            # 标记以使用过，不能重复使用
            board[x][y] = ''

            # 2. 如果等于 idx 结束
            if idx == len(word) - 1:
                return True

            # 3. 继续寻找下一个 idx ： 这里可以定义一个 action， 通过循环遍历，不用每步单独写开
            # 向上
            if x - 1 >= 0:
                flag = isExist(board, x - 1, y, idx + 1)
                # 增加这个，如果当前结果已经是 True了， 没必要再去遍历其他分支了，增加性能
                if flag: return flag
            # 向右
            if y + 1 < len(board[0]):
                flag = isExist(board, x, y + 1, idx + 1)
                if flag: return flag
            # 向左
            if y - 1 >= 0:
                flag = isExist(board, x, y - 1, idx + 1)        
                if flag: return flag
            # 向下
            if x + 1 < len(board):
                flag = isExist(board, x + 1, y, idx + 1)
                if flag: return flag

            # 4. 回溯，解除当前位置的修改    
            board[x][y] = tempC

        for i in range(len(board)):
            for j in range(len(board[0])):
                if board[i][j] == word[0]:
                    flag = isExist(board, i, j, 0)
                    if flag: return True

        return False